#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

string hexToBinary(const string& hex) {
    string binary;
    for (char c : hex) {
        int val;
        if (isdigit(c)) val = c - '0';
        else val = toupper(c) - 'A' + 10;
        string bits;
        for (int i = 3; i >= 0; --i) {
            bits += (val & (1 << i)) ? '1' : '0';
        }
        binary += bits;
    }
    // Remove leading zeros
    size_t first = binary.find_first_not_of('0');
    if (first != string::npos) {
        binary = binary.substr(first);
    } else {
        binary = "0";
    }
    return binary;
}

string addOne(const string& s) {
    if (s.empty()) return "1";
    string rev = s;
    reverse(rev.begin(), rev.end());
    vector<char> rev_vec(rev.begin(), rev.end());
    int carry = 1;
    for (size_t i = 0; i < rev_vec.size() && carry; ++i) {
        if (rev_vec[i] == '1') {
            rev_vec[i] = '0';
        } else {
            rev_vec[i] = '1';
            carry = 0;
        }
    }
    if (carry) {
        rev_vec.push_back('1');
    }
    reverse(rev_vec.begin(), rev_vec.end());
    return string(rev_vec.begin(), rev_vec.end());
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int m;
        string hex_n;
        cin >> m >> hex_n;

        string binary_n = hexToBinary(hex_n);
        if (binary_n.empty()) binary_n = "0";

        string s_plus_1 = addOne(binary_n);
        int len_p = s_plus_1.size();

        vector<int> prefix_mod(len_p, 0);
        prefix_mod[0] = (s_plus_1[0] == '1') ? 1 : 0;
        for (int i = 1; i < len_p; ++i) {
            prefix_mod[i] = (prefix_mod[i-1] * 2LL + (s_plus_1[i] == '1')) % MOD;
        }

        vector<long long> pow2(len_p + 2, 1);
        for (int i = 1; i < len_p + 2; ++i) {
            pow2[i] = (pow2[i-1] * 2LL) % MOD;
        }

        vector<long long> suffix_mod(len_p, 0);
        suffix_mod[len_p - 1] = (s_plus_1.back() == '1') ? 1 : 0;
        for (int i = len_p - 2; i >= 0; --i) {
            int exponent = (len_p - 1) - i;
            long long bit_val = (s_plus_1[i] == '1') ? pow2[exponent] : 0;
            suffix_mod[i] = (bit_val + suffix_mod[i + 1]) % MOD;
        }

        long long sum_total = 0;
        for (int k = 0; k < len_p; ++k) {
            int pos = len_p - 1 - k;
            bool bit_is_one = (pos >= 0 && pos < len_p) && (s_plus_1[pos] == '1');

            int t = len_p - (k + 1);
            long long high_mod = 0;
            if (t > 0) {
                if (t - 1 < len_p) {
                    high_mod = prefix_mod[t - 1];
                }
            }

            long long pow2k = pow2[k];
            long long high_part = (high_mod * pow2k) % MOD;

            long long rem_part = 0;
            if (bit_is_one) {
                int low_pos = len_p - k;
                if (low_pos < len_p) {
                    rem_part = (low_pos >= 0) ? suffix_mod[low_pos] : 0;
                }
            }

            long long current_count = (high_part + rem_part) % MOD;
            long long k_sq = (1LL * k * k) % MOD;
            long long term = (current_count * (k_sq + 1)) % MOD;
            sum_total = (sum_total + term) % MOD;
        }

        cout << sum_total % MOD << '\n';
    }

    return 0;
}